1. Field of the Invention
The present invention relates to a buffer space allocation method and related packet switch, and more particularly, to a buffer space allocation method and related packet switch adaptively adjusting the dedicated buffer space for an output queue according to the number of packets in the output queue.
2. Description of the Prior Art
With the rapid development of the Internet, the packet switch technique is also improving day by day to meet the requirements of transmission quality and rate of the public. Based on different queue allocation method, the packet switch can be catalogued into the output queued switch, the input queued switch, the combined input output queued switch, etc, wherein the output queued switch allocates buffer resources for output ports of packet switch, and is most effective. The most common output queued switch scheme is the shared-buffer output queued switch, wherein the packet buffer is shared among all output ports. Theoretically, the effectiveness of buffer of shared buffer packet switch is higher than that of non-shared buffer packet switch.
Please refer to FIG. 1A to FIG. 1C. The FIG. 1A to FIG. 1C are diagrams of resources allocations of a buffer of a shared-buffer output queued switch according to the prior art, which assume the bidirectional network ports P1-P4 of output queued switch share the buffer. FIG. 1A indicates that the whole buffer are common to the network ports P1-P4, while this allocation method may easily results in a starvation phenomenon that no buffer space is available for parts of the network ports; for example, all of the buffer space is occupied by the network ports P1 and P4, while no buffer space is available for the network ports P2 and P3. To avoid the above starvation phenomenon, the prior art has provided another relatively fair allocation method, as shown in FIG. 1B. FIG. 1B indicates that the buffer is equally shared by the network ports P1-P4, while each of the network ports has dedicated buffer space without sharing. Nevertheless, in practice, the packet throughput of each network port may not equal. When packets are inputted from the network ports P1, P2, and P3, and all purpose to be outputted from the network port P4, a packet loss will occur under the situation that the dedicated buffer space reserved for the network port P4 has been used up. The allocation method of FIG. 1C is the mixture of FIG. 1A and FIG. 1B that parts of the buffer space is equally shared by the network ports P1-P4, whereas the others are common to the network ports P1-P4, called mixed sharing mode. As regards the above three allocation methods, the mixed sharing mode in FIG. 1C acquires a better balance between the starvation phenomenon and the effectiveness of buffer, and is most commonly used in present packet switches. In addition, the dedicated buffer space reserved for each network port can be further divided into a plurality of subspace according to the transmission services with different priorities, such as audio, video, or data, corresponding to different output queues.
Please refer to FIG. 2. FIG. 2 is a schematic diagram of a packet switch 20 according to the prior art. The packet switch 20 is a shared-buffer output queued switch comprising a buffer 200, a buffer management unit 202 and four bidirectional network ports P1-P4, wherein the allocation method of the buffer 200 belongs to the mixed sharing mode illustrated in FIG. 1C. The buffer management unit 202 is coupled to the buffer 200 and the network ports P1-P4, which allocates available buffer resources to corresponding output ports to temporary store packets according to buffer resources request signals received by each input port, and removes the occupational status of buffer resources after the packet transmission is finished. The network port P1 is a hot spot, such as a wide area network port of a router. It can be shown from FIG. 2 that only few packets are waiting to be outputted from the network ports P2, P3, or P4, and there is surplus of the dedicated buffer space reserved for the network ports, whereas packets waiting to be outputted from the network port P1 is too many and exhausts the dedicated buffer space, and the common buffer space for all network ports must be utilized. The maximum buffer space that can be utilized by network port P1 equals the dedicated buffer space reserved for the network port P1 and the common buffer space; the network ports P2, P3, and P4 maintains each dedicated buffer space.
Please note that FIG. 2 takes 4 network ports as an example for the sake of convenience. In practice, the number of network ports in a packet switch is usually mounted to a few tens. In a high network port density packet switch, only few output queues of network ports may have a large number of packets waiting to be transmitted, while most of the output queues of network ports do not contain too many packets. Under the circumstances, if the mixed sharing mode in FIG. 1C is applied, most of the buffer space would be occupied by network ports that do not need to transmit too many packets, and hence the common buffer space is curtailed. Therefore, the network ports which need more buffer space have no sufficient buffer space to be utilized, resulting in a large decrease of effectiveness of buffer and an easy packet loss. That is, the prior art mixed sharing mode buffer allocation cannot raise the effectiveness of buffer of the high network port density packet switch.